/**
 * 实现给定数字数组，求[1, n]之间只用数组中数字作为数位的数的数量
 * 本质上与不含4是一致的
 * 注意前导零是有影响的
 */
using llt = long long;

vector<int> G;
vector<int> Valid;

llt D[11];
llt dfs(int pos, bool lead, bool limit){
    if(-1 == pos) {
        return lead ? 0 : 1; // 纯0不能计算
    }
    if(not lead and not limit and -1 != D[pos]) {
        return D[pos];
    }
    int last = limit ? G[pos] : 9;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(0 == i and lead){ // 仍然处在前导0范围内，即使0不在Valid内也可以搜索
            ans += dfs(pos - 1, true, limit&&last==i);
        }else if(find(Valid.begin(), Valid.end(), i) != Valid.end()){ // 如果是合法的数字就可以继续搜索
            ans += dfs(pos - 1, false, limit&&last==i);
        }
        
    }
    if(not lead and not limit){
        D[pos] = ans;
    }    
    return ans;
}

llt digitDP(llt n){
    G.clear();
    while(n){
        G.emplace_back(n % 10);
        n /= 10;
    }
    return dfs(G.size()-1, true, true);
}


class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        memset(D, -1, sizeof(D));
        Valid.clear(); // 全局变量，在力扣上提交要清空
        for(const auto & s : digits) Valid.emplace_back(s[0] - '0');
        return digitDP(n);
    }
};